/*
* 2010
* Authors: Sergey Lapin <lapanoid@gmail.com>
* Feedback Arc Set class realisation
*/
#include "../stdafx.h"
#include "fas_greedy.h"
#include <list>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <fstream>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/properties.hpp>
#include <iostream>

bool FasGreedy::HaveCycle(const Graph &worker)
{
    Graph hcycle_proc = worker; 
    size_t num, newnum;
    num = num_vertices(hcycle_proc);

    IsSink sink;
    IsSource sourse;
    while (num) {        
        DeleteByProperty(hcycle_proc, &sink, true);
        DeleteByProperty(hcycle_proc, &sourse, false);
        newnum = num_vertices(hcycle_proc);
        if (newnum == num) {
            return true;
        }
        num = newnum;
    }
    return false;
}

void FasGreedy::DeleteByProperty(Graph &worker, 
                           IsProperty *isproperty,
                           bool IsReverse,
                           list<Vertex> *vertex_seq)
{
    bool res = false;
    list<Vertex> toDelete;
    Vertex_Iterator vi, vend;
    tie(vi, vend) = vertices(worker);    
    for (; vi != vend; vi++) {
        if((*isproperty)(*vi, worker)) {
            toDelete.push_back(*vi);
            res = true;
        }
    }
    list<Vertex>::iterator tmp;
    tmp = toDelete.begin();    
    for (; tmp != toDelete.end(); tmp++) {
        ClearAndRemove(*tmp, worker);
        if (vertex_seq) {
            if (IsReverse) {
                vertex_seq->push_front(*tmp);                            
            } else {
                vertex_seq->push_back(*tmp);            
            }    
        }
    }  
    
    if (res) {
        DeleteByProperty(worker, isproperty, IsReverse, vertex_seq);        
    }
}

void FasGreedy::GR_procedure(list<Vertex_Number> *num_seq, FasDirnumerator &dirnum, Graph &worker)
{
	LogStream logcout( &cout);
    list<Vertex> vertex_seq;
    logcout << "Start: GR_procedure" << endl;
    list<Vertex> s1, s2;    
    Vertex maxDelta;

    logcout << "Num of Vertices & Edges: " << endl;
    size_t num = num_vertices(worker);
    logcout << num;    
    logcout << " ";
    size_t num_e = num_edges(worker);
    logcout << num_e;
    for (size_t i = 0; i < 1 + GetNumberOfDigits(num_e) + GetNumberOfDigits(num); i++) {
        logcout << '\b' << ' ' << '\b';
    }
    IsSink sink;
    IsSource sourse;
    while (num) {
        DeleteByProperty(worker, &sink, true, &s2);
        DeleteByProperty(worker, &sourse, false, &s1);
        
        num = num_vertices(worker);
        if (!num) {
            break;
        }
        maxDelta = FindMaxDelta(worker);
        s1.push_back(maxDelta);
        ClearAndRemove(maxDelta, worker);
        num = num_vertices(worker);
        logcout << num;
        num_e = num_edges(worker);
        logcout << " ";        
        logcout << num_e;        
        for (size_t i = 0; i < 1 + GetNumberOfDigits(num_e) + GetNumberOfDigits(num); i++) {
            logcout << '\b';
        }

    }
    vertex_seq.insert(vertex_seq.begin(), s2.begin(), s2.end());
    vertex_seq.insert(vertex_seq.begin(), s1.begin(), s1.end());  
    dirnum.Map(vertex_seq, num_seq);
}

/* Computes arcs to delete and delete them*/
void FasGreedy::MakeAcyclicGreedy(Graph &worker)
{    
	LogStream logcout( &cout);
    logcout << "Start MakeAcyclicGreedy function" << endl;

    list<Vertex> vertex_seq;
    list<Vertex_Number> num_seq;    

    // temporary graph initialization
    Graph gr_proc = worker;  

    VertexIndexation(gr_proc);
    /* Make compliance between temporary and working graph by numerating them */
    FasDirnumerator dirnum(&(worker));
    FasInvnumerator invnum(&(gr_proc));
    FasDirnumerator dirnum2(&(gr_proc));

    GR_procedure(&num_seq, dirnum, worker);

    // worker vertex sequence -> vertex sequence numbers    

    logcout << "Vertex-numeration sequence is:";
#ifdef _DEBUG
    copy(num_seq.begin(), num_seq.end(), ostream_iterator<Vertex_Number>(cout, ""));    
#endif
    logcout << endl;
    logcout << "End succesfully: GR_procedure" << endl;
    vertex_seq.clear();

    // vertex sequence numbers -> gr_proc.worker vertex sequence
    invnum.Map(num_seq, &vertex_seq);

    // gr_proc.worker leftwarc arcs deleting
    EdgeIntersect(num_seq, dirnum2, gr_proc);

    worker = gr_proc;
}

size_t FasGreedy::GetNumberOfDigits(size_t number)
{
    if (number == 0) { 
        return 1; 
    }
    size_t count = 0;
    while (number != 0) {
      number /= 10;
      ++count;
    }

    return count;
}
void FasGreedy::EdgeIntersect(list<Vertex_Number> &vertex_seq, FasDirnumerator &dirnum, Graph &worker)
{
	LogStream logcout( &cout);
    logcout << "Start: EdgeIntersect" << endl;
    pair<Edge_Iterator, Edge_Iterator> res = edges(worker);
    list<Edge> toDelete;
    Edge_Iterator vi = res.first;     
   
    size_t counter = 0;
    for (; vi != res.second; vi++, counter++) {
        if(LeftArc(dirnum.Map(source(*vi, worker)),
                   dirnum.Map(target(*vi, worker)), vertex_seq)) {
            toDelete.push_back(*vi);
        }        
    }   
    
    list<Edge>::iterator tmp;
    tmp = toDelete.begin();    
    for (; tmp != toDelete.end(); tmp++) {
        remove_edge(*tmp, worker);
    }    
    logcout << "End succesfully:" ;
}

bool FasGreedy::LeftArc(Vertex_Number left, Vertex_Number right, 
                  list<Vertex_Number> &vertex_seq)
{
	if (right == left) {
        return true;
    }
    list<Vertex_Number>::iterator vi;
    vi = vertex_seq.begin();    
    for (; vi != vertex_seq.end(); vi++) {
        if (left == *vi) {
            return false;
        }
        if (right == *vi) {
            return true;
        }
    }
    return false;    
}

void FasGreedy::VertexIndexation(Graph &worker)
{
	LogStream logcout( &cout);
    logcout << "Vertex indexation" << endl;
    property_map<Graph, vertex_index_t>::type index = get(vertex_index, worker);

    // initialize the vertex_index property values
    Vertex_Iterator vi, vend;
    Vertex_Number cnt = 0;
    for(tie(vi,vend) = vertices(worker); vi != vend; vi++) {
        put(index, *vi, cnt++);
    }
}

Vertex FasGreedy::FindMaxDelta(const Graph &worker)
{
    Vertex res;
    Vertex_Iterator vi, vend;
    tie(vi, vend) = vertices(worker);
    res = *vi;

    for (; vi != vend; ++vi) {
        if (CalcDelta(res, worker) < CalcDelta(*vi, worker)) {
            res = *vi;
        }
    }		
    return res;
}

int FasGreedy::CalcDelta(Vertex v, const Graph &worker)
{       
    return out_degree(v, worker) - in_degree(v, worker);
}

void FasGreedy::ClearAndRemove (Vertex v, Graph &worker)
{
    clear_vertex(v, worker);
    remove_vertex(v, worker);    
}